Симметричное справедливое разрезание торта

Симметричное справедливое разрезание торта — это вариант задачи справедливого разрезания торта, в котором справедливость оценивается не только по частям торта, но и по участию в разрезании.

Сущность

Рассмотрим пример: пусть дан торт — и его нужно разделить между Алисой и Джорджем, вкусы которых различаются, так, чтобы каждый из них чувствовал, что его доля разрезана и выбрана справедливо, то есть так, чтобы у каждого из них ценность доли была не меньше половины ценности всего торта. Можно было бы использовать классическое решение «дели и выбирай»: Алиса режет торт на две такие части, которые для неё являются равноценными, а Джордж выбирает кусок, который он считает более ценным. Однако в этом решении есть изъян: Алиса получает всегда долю с ценностью 1/2, а вот Джордж может получить долю, ценность которой больше 1/2. Поэтому это разрезание называется справедливым, но несимметричным, то есть Алиса не видит ничего страшного в том, какую долю выбрал Джордж, но чувствует несправедливым то, что именно Джордж выбирал долю, а она разрезала торт.

Рассмотрим другое решение: Алиса и Джордж оба помечают свою границу (в простейшем случае — параллельные либо совпадающие отрезки), которая, с точки зрения каждого из них, делит торт на равноценные половины. Затем торт режется ровно посередине между этими границами: обозначим за a объёмную часть левой доли торта, на которую поделила Алиса, а за g — объёмную часть левой доли торта, на которую поделил Джордж, — тогда торт нужно резать пополам на две доли, объёмная часть левой из каких равна $(a+g)/2$. Если a < g, то Алиса получает кусок слева (ценность которой больше, чем поделила Алиса), а Джордж забирает кусок справа (ценность которой тоже больше). Если же a > g, то Алиса, наобороот, получает правый кусок, а Джордж — левый. Поэтому данное решение задачи называется справедливым и симметричным.

Данную идею первыми предложили Монабе и Окамото, которые назвали её метасвободной от зависти.

Было предложено несколько вариантов симметричного справедливого разрезания торта:

• Анонимное справедливое разрезание торта требует, чтобы не только значения были одинаковыми, но и сами куски были равны. Из этого следует симметричная справедливость, но условие строже. Например, такое разрезание не обеспечивается вышеприведённой симметричной процедурой «дели-и-выбирай», поскольку в случае a=g, первый агент получает всегда самый левый кусок, а второй всегда получает самый правый кусок.
• Аристотелево справедливое разрезание торта требует только, чтобы агенты с идентичными мерами получили куски с тем же самым значением оценки. Из этого следует симметричная справедливость, но условие слабее. Например, оно удовлетворяется асимметричной версией процедуры «дели-и-выбирай» — если оценки агентов идентичны, оба игрока ровно по 1/2.

Определения

Имеется торт C, обычно представляемый как одномерный отрезок. Имеется n человек, и каждый участник дележа i имеет функцию оценки V_i, которая отображает подмножества C в неотрицательные числа.

Процедура дележа — это функция F, которая отображает n функций оценок в разбиение отрезка C. Кусок, который функция F выделяет агенту i, обозначим как $F(V_{1},\dots ,V_{n};i)$.

Симметричная процедура

Процедура дележа F называется симметричной, если при любой перестановке p индексов (1,…,n) и любом i

$V_{i}(F(V_{1},\dots ,V_{n};i))=V_{i}(F(V_{p(1)},\dots ,V_{p(n)};p^{-1}(i)))$

В частности, при n=2 процедура симметрична, если

$V_{1}(F(V_{1},V_{2};1))=V_{1}(F(V_{2},V_{1};2))$ и $V_{2}(F(V_{1},V_{2};2))=V_{2}(F(V_{2},V_{1};1))$.

Это означает, что агент 1 получает то же самое значение независимо от того, играет ли он первым или вторым, и то же самое верно для агента 2.

В другом примере, когда n=3, из требования симметрии следует (среди прочего):

$V_{1}(F(V_{1},V_{2},V_{3};1))=V_{1}(F(V_{2},V_{3},V_{1};3))=V_{1}(F(V_{3},V_{1},V_{2};2))$

Анонимная процедура

Процедура дележа F называется анонимной, если для любой перестановки p индексов (1,…,n) и для любого $i$

$F(V_{1},\dots ,V_{n};i)=F(V_{p(1)},\dots ,V_{p(n)};p^{-1}(i))$

Любая анонимная процедура симметрична, поскольку в случае равенства кусков их оценки заведомо равны.

Обратное, однако, не верно — возможно, что перестановка даёт агенту различные куски с одинаковыми значениями.

Аристотелева процедура

Процедура дележа F называется аристотелевой, если при $V_{i}=V_{k}$:

$V_{i}(F(V_{1},\dots ,V_{n};i))=V_{k}(F(V_{1},\dots ,V_{n};k))$

Критерий называется по имени Аристотеля, который писал в своей книге по этике: «… когда при одинаковом владении предоставляются неравные доли, или когда лица не равны при равных долях, растёт число споров и жалоб».

Любая симметричная процедура аристотелева. Пусть p будет перестановкой, меняющей местами i и k. Из симметрии следует, что

$V_{i}(F(V_{1},\dots ,V_{i},\dots ,V_{k},\dots ,V_{n};i))=V_{i}(F(V_{1},\dots ,V_{k},\dots ,V_{i},\dots ,V_{n};k))$

Но, поскольку V_i=V_k, эти две последовательности мер идентичны, откуда следует определение аристотелевости.

Более того, любая процедура завистливого разрезания торта аристотелева — из отсутствия зависти следует, что

$V_{i}(F(V_{1},\dots ,V_{n};i))\geqslant V_{i}(F(V_{1},\dots ,V_{n};k))V_{k}(F(V_{1},\dots ,V_{n};k))\geqslant V_{k}(F(V_{1},\dots ,V_{n};i))$

Однако, поскольку $V_{i}=V_{k}$, из двух противоположных неравенств следует, что оба значения равны.

Однако процедура, удовлетворяющая более слабому условию пропорционального разрезания торта не обязательно будет аристотелевой. Чиз привёл пример с 4 агентами, в котором процедура Эвена — Паза для пропорционального разрезания торта может дать различные значения для агентов с идентичными оценочными мерами.

Следующее подытоживает отношения между критериями:

• Анонимный $\to$ Симметричный $\to$ Аристотелев
• Без зависти $\to$ Аристотелев
• Без зависти $\to$ Пропорциональный

Процедуры

Любая процедура может быть сделана «априори симметричной» путём рандомизации. Например, при асимметричной процедуре «дели-и-выбирай» делящий может быть выбран бросанием монеты. Однако такая процедура не будет симметричной по факту. Поэтому исследования относительно симметричного справедливого разрезания торта фокусируются на детерминированных алгоритмах.

Монабе и Окамото предложили симметричные детерминированные процедуры без зависти («метасвободные от зависти») для двух и трёх агентов.

Николо и Ю предложили протокол анонимного и эффективного по Парето дележа без зависти для двух агентов. Протокол реализует равновесие, совершенное по подыграм, в предположении, что каждый агент обладает полной информацией об оценках других агентов.

Процедура симметричного разрезания и выбора для двух агентов изучали эмпирически в лабораторных экспериментах. Альтернативными процедурами симметричного справедливого разрезания торта для двух участников являются самая правая отметка и самый левый остаток.

Чиз предложил несколько процедур:

• Общая схема преобразования любой процедуры завистливого дележа в симметричную детерминированную процедуру: проводим исходную процедуру n! раз, по разу для каждой перестановки агентов, и выбираем результат согласно топологическому критерию (то есть, по минимуму разрезов). Эта процедура становится практически неприменимой при больших n.
• Аристотелева пропорциональная процедура для n агентов, которая требует $O(n^{3})$ запросов и полиномиальное число арифметических операций.
• Симметричная пропорциональная процедура для n агентов, которая требует $O(n^{3})$ запросов, но может требовать экспоненциальное число арифметических операций.

Аристотелева пропорциональная процедура

Аристотелева процедура Чиза для пропорционального разрезания торта расширяет процедуру «одиночный делящий». Для удобства нормализуем функции оценок, чтобы значение всего торта для всех агентов было равно n. Целью является выделение каждому агенту доли, которая не меньше 1.

1. Выбирается один игрок произвольным образом, который называется делящим, он режет торт на n частей, которые он/она оценивает ровно в 1.
2. Строится двудольный граф $G=(X+Y,E)$, в котором каждая вершина X является агентом, каждая вершина Y является куском торта и имеется ребро между агентом x и куском торта y тогда и только тогда, когда x оценивает кусок y по меньшей мере в 1.
3. Ищем максимальное по размеру паросочетание без зависти (ПБЗ) в G (паросочетание, в котором нет агента, не принадлежащего паросочетанию, но смежного принадлежащено паросоченанию куску торта). Заметим, что делящий смежен всем n кускам торта, так что $|N_{G}(X)|=n\geqslant |X|$ (где $N_{G}(X)$ является множеством соседей X в Y). Следовательно, непустое паросочетание без зависти существует. Предположим без потери общности, что ПБЗ сопоставляет агентов 1,…,k кускам $X_{1},\dots ,X_{k}$, оставляя без соответствия агентов и куски от k+1 др n.
4. Для любого i из 1,…,k, для которого $V_{i}(X_{i})=1$, отдаём X_i агенту i. Теперь делящему и всем агентам, чьи функции оценок идентичны функции делящего, назначены куски, имеющие одинаковые значения.
5. Рассмотрим теперь агентов i из 1,…,k, для которых $V_{i}(X_{i})>1$. Разобьём их на подмножества с равными векторами оценок кусков $X_{1},\dots ,X_{n}$. Для каждого подмножества рекурсивно делим их куски среди них (например, если агенты 1, 3, 4 согласны со значениями всех кусков 1,…,k, то делим куски $X_{1},X_{3},X_{4}$ рекурсивно среди них). Теперь все агенты, функции оценок которых идентичны, назначены тем же самым подмножествам и они делят подторт, значение которого среди них больше, чем их число, так что предусловие для рекурсии выполнено.
6. Рекурсивно делим нераспределённые куски $X_{k+1},\dots ,X_{k}$ среди нераспределённых агентов. Заметим, что согласно отсутствия зависти в паросочетании каждый не распределённый агент оценивает каждый распределённый кусок меньше чем в 1, так что значения оставшихся кусков не меньше числа агентов, так что предусловие для рекурсии сохраняется.

Литература

• Yoshifumi Manabe, Tatsuaki Okamoto. Meta-envy-free Cake-cutting Protocols // Proceedings of the 35th International Conference on Mathematical Foundations of Computer Science. — Berlin, Heidelberg: Springer-Verlag, 2010. — ISBN 9783642151545.
• Antonio Nicolò, Yan Yu. Strategic divide and choose // Games and Economic Behavior. — 2008. — Т. 64, вып. 1. — ISSN 0899-8256. — doi:10.1016/j.geb.2008.01.006.
• Guillaume Chèze. Don't cry to be the first! Symmetric fair division algorithms exist. — 2018. — arXiv:1804.03833v1.
• Maria Kyropoulou, Josué Ortega, Erel Segal-Halevi. Fair Cake-Cutting in Practice // Proceedings of the 2019 ACM Conference on Economics and Computation. — New York, NY, USA: ACM, 2019. — ISBN 9781450367929. — doi:10.1145/3328526.3329592. — arXiv:1810.08243.
• Erel Segal-Halevi, Balázs R. Sziklai. Resource-monotonicity and population-monotonicity in connected cake-cutting // Mathematical Social Sciences. — 2018. — Vol. 95. — ISSN 0165-4896. — doi:10.1016/j.mathsocsci.2018.07.001. — arXiv:1703.08928.
• Josue Ortega. Obvious Manipulations in Cake-Cutting. — 2019. — arXiv:1908.02988v1.
• Erel Segal-Halevi, Elad Aigner-Horev. Envy-free Matchings in Bipartite Graphs and their Applications to Fair Division. — 2019. — arXiv:1901.09527v2.